\input{euler.tex}

\begin{document}

\problem[94]{Almost Equilateral Heronian Triangles}

A \emph{Heronian triangle} is a triangle whose side lengths and area are all integral numbers. It is easily seen that no equilateral Heronian triangle exists. However, the \emph{almost equilateral} triangle 5-5-6 has an area of 12 square units. Here we define an \emph{almost equilateral} triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all \emph{almost equilateral} triangles with integral side lengths and area and whose perimeters do not exceed $10^9$.

\solution

Let the side lengths of an almost equilateral Heronian triangle be 
\[
(2a,2a \pm 1,2a \pm 1) .
\]
The height of the triangle corresponding to the unequal side is 
\begin{equation}
h = \sqrt{(2a \pm 1)^2 - a^2}, \label{eq:94.1}
\end{equation}
and the area of the triangle is $S = ah$. It is easy to see that $a$ must be an integer in order for the area to be integral.

Now the task is to find all integer solutions $(h,a)$ to equation \eqref{eq:94.1}. To do this, rewrite equation \eqref{eq:94.1} as
\begin{align}
h^2 &= (2a \pm 1)^2 - a^2 \notag \\
&= 3a^2 \pm 4a + 1 \notag \\
&= 3 \left( a \pm \frac{2}{3} \right)^2 - \frac13 \notag ,
\end{align}
and multiply both sides by 9 to yield
\begin{equation}
(3h)^2 = 3(3a\pm 2)^2 - 3 . \label{eq:94.2}
\end{equation}
By a simple variable substitution $x = 3h, y = 3a \pm 2$, we get the following Pell equation:
\begin{equation}
x^2 - 3 y^2 = -3 . \label{eq:94.3}
\end{equation}
Each solution $(x,y)$ to equation \eqref{eq:94.3} corresponds to zero or one solution $(h,a)$ to equation \eqref{eq:94.2}, depending on whether $a = (y \mp 2) / 3$ is integral. 

To solve equation \eqref{eq:94.3}, first find its fundamental solution $(0,1)$. Then note the related standard Pell equation
\[
x^2 - 3 y^2 = 1
\]
has basic solution $(2,1)$. Hence all the rest solutions can be generated by standard techniques. The termination condition is $6a \pm 2 \le L$, which is equivalent to $y \le L/2 \pm 1$, where $L = 10^9$ is the maximum perimeter to find.

\complexity

Time complexity: $\BigO(\log L)$.

Space complexity: $\BigO(1)$.

\answer

518408346


\end{document} 